Various topologies are known in the art for connecting network switches to one another in packet networks. An example topology is referred to as Fat-Tree topology. Fat-Tree networks were originally defined by Leiserson in “Fat-Trees: Universal Networks for Hardware Efficient Supercomputing,” IEEE Transactions on Computers, volume C-34, no. 10, 1985, pages 892-901, which is incorporated herein by reference.
Fat-Tree topologies having special properties are sometimes classified into families, such as k-ary n-trees, Generalized Fat-Trees (GFT) and Extended GFTs (EGFT). For example, Öhring et al. define extended and generalized Fat Trees, in “On Generalized Fat Trees,” Proceedings of the 9th International Symposium on Parallel Processing, 1995, page 37, which is incorporated herein by reference.
Packet routing in Fat-Tree networks is addressed, for example, by Gomez et al., in “Deterministic versus Adaptive Routing in Fat-Trees,” IEEE International Symposium on Parallel and Distributed Processing, Long Beach, Calif., USA, 2007, pages 1-8; by Xuan-Yi Lin et al., in “A multiple LID routing scheme for fat-tree-based InfiniBand networks,” Proceedings of the 18th Symposium on Parallel and Distributed Processing, 2004; and by Zahavi, in “D-Mod-K Routing Providing Non-Blocking Traffic for Shift Permutations on Real Life Fat Trees,” CCIT Technical Report #776, Technion-Israel Institute of Technology, Haifa, Israel, August, 2010, which are incorporated herein by reference.